'''
https://leetcode.cn/problems/daily-temperatures/description/
'''
from collections import deque
from typing import List


class Solution:

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # [91, 3, 2, 1, 1]  90
        n = len(temperatures)
        ans = [0] * n
        stack = deque()
        for i, temperature in enumerate(temperatures):
            while stack and temperature > temperatures[stack[-1]]:
                t = stack.pop()
                ans[t] = i - t
            stack.append(i)
        return ans

temperatures = [73,74,75,71,69,72,76,73]
print(Solution().dailyTemperatures(temperatures))